Search results for "Biconnected graph"

showing 2 items of 2 documents

Protein-protein interaction network querying by a "focus and zoom" approach

2008

We propose an approach to network querying in protein-protein interaction networks based on bipartite graph weighted matching. An algorithm is presented that first “focuses” the potentially relevant portion of the target graph by performing a global alignment of this one with the query graph, and then “zooms” on the actual matching nodes by considering their topological arrangement, hereby obtaining a (possibly) approximated occurrence of the query graph within the target graph. Approximation is related to node insertions, node deletions and edge deletions possibly intervening in the query graph. The technique manages networks of arbitrary topology. Moreover, edge labels are used to represe…

Bioinformatics network analysisTheoretical computer scienceVoltage graphGraph (abstract data type)Folded cube graphAdjacency matrixNull graphBiconnected graphButterfly graphSimplex graphMathematicsofComputing_DISCRETEMATHEMATICSMathematics
researchProduct

An efficient algorithm for stopping on a sink in a directed graph

2013

Abstract Vertices of an unknown directed graph of order n are revealed one by one in some random permutation. At each point, we know the subgraph induced by the revealed vertices. Our goal is to stop on a sink, a vertex with no out-neighbors. We show that if a sink exists this can be achieved with probability Θ ( 1 / n ) , which is best possible.

Factor-critical graphDiscrete mathematicsApplied MathematicsNeighbourhood (graph theory)Directed graphManagement Science and Operations ResearchBiconnected graphIndustrial and Manufacturing EngineeringHypercube graphCombinatoricsWheel graphPath graphGraph factorizationSoftwareMathematicsofComputing_DISCRETEMATHEMATICSMathematicsOperations Research Letters
researchProduct